package combination;

import java.util.*;

/**
 * @program: javase
 * @description: 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 * @author: luolidong
 * @create: 2021-06-25 17:48
 * @version: 1.0
 */
/**
* visited[] 保证当前元素本次循环不再访问
 * 如果有重复元素，最后会重复，
 * 1.可以使用set保存
 * 2.先排序，在递归的时候判断
*/
public class StringCombination {
//    boolean[] visit;
//    public String[] permutation(String s) {
//        if (s.length() == 0) return new String[0];
//        visit = new boolean[s.length()];
//        Set<String> list = new HashSet<>();
//        char[] chars = s.toCharArray();
//        dfs(list, new StringBuilder(),  chars);
//       return list.toArray(new String[chars.length]);
//    }
//
//    private void dfs(Set<String> list, StringBuilder sb, char[] chars) {
//        if (sb.length() == chars.length) {
//            list.add(new String(sb));
//            return;
//        }
//        for (int i = 0; i < chars.length; i++) {
//            if (visit[i]) continue;
//            visit[i] = true;
//            sb.append(chars[i]);
//            dfs(list, sb, chars);
//            visit[i] = false;
//            sb.deleteCharAt(sb.length() - 1);
//        }
//    }
    //先排序
    boolean[] visit;
    public String[] permutation(String s) {
        if (s.length() == 0) return new String[0];
        visit = new boolean[s.length()];
        List<String> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        dfs(list, new StringBuilder(),  chars);
       return list.toArray(new String[chars.length]);
    }

    private void dfs(List<String> list, StringBuilder sb, char[] chars) {
        if (sb.length() == chars.length) {
            list.add(new String(sb));
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (visit[i]||(i-1>=0&&!visit[i-1]&&chars[i]==chars[i-1])) continue;
            visit[i] = true;
            sb.append(chars[i]);
            dfs(list, sb, chars);
            visit[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        String[] abcs = new StringCombination().permutation("abac");
        System.out.println(Arrays.toString(abcs));
    }
}
